{
  "metadata": {
    "kernelspec": {
      "name": "python",
      "display_name": "Python (Pyodide)",
      "language": "python"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "python",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8"
    }
  },
  "nbformat_minor": 4,
  "nbformat": 4,
  "cells": [
    {
      "cell_type": "code",
      "source": "def extended_euclidean_algorithm(a, b):\n    x1, y1, x2, y2 = 1, 0, 0, 1\n    \n    while b:\n        q = a // b\n        a, b = b, a % b\n        x1, x2 = x2, x1 - q * x2\n        y1, y2 = y2, y1 - q * y2\n\n    return a, x1, y1\n\n# Example\nnum1 = 30\nnum2 = 24\ngcd_result, x, y = extended_euclidean_algorithm(num1, num2)\nprint(f'The greatest common divisor of {num1} and {num2} is {gcd_result}')\nprint(f\"The integer solution that satisfies Bezu's equation is：{num1}*{x} + {num2}*{y} = {gcd_result}\")",
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "text": "The greatest common divisor of 30 and 24 is 6\nThe integer solution that satisfies Bezu's equation is：30*1 + 24*-1 = 6\n",
          "output_type": "stream"
        }
      ],
      "execution_count": 2
    },
    {
      "cell_type": "code",
      "source": "def gcd(a, b):\n    if a < b :\n          a, b = b, a\n    while a % b != 0 :\n          a, b = b, a % b\n    return b\n\ndef ext_gcd(a, b):\n    if b == 0:\n        return 1, 0\n    else:\n        x, y = ext_gcd(b, a%b)\n        x, y = y, x - (a//b) * y\n        return x, y\n    \nnum1 = 3\nnum2 = 7\nx, y = ext_gcd(num1, num2)\nprint(f'The greatest common divisor of {num1} and {num2} is {gcd(num1, num2)}')\nprint(f\"The integer solution that satisfies Bezu's equation is：{num1}*{x} + {num2}*{y} = {gcd(num1, num2)}\")",
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "text": "The greatest common divisor of 3 and 7 is 1\nThe integer solution that satisfies Bezu's equation is：3*-2 + 7*1 = 1\n",
          "output_type": "stream"
        }
      ],
      "execution_count": 3
    },
    {
      "cell_type": "code",
      "source": "",
      "metadata": {
        "trusted": true
      },
      "outputs": [],
      "execution_count": null
    }
  ]
}